package leetcode_core.leetcode_4;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月16日 10:18
 */
public class isBipartiteBFS {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        boolean[] color = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        boolean ok = true;
        visited[0] = true;
        q.offer(0);
        while (!q.isEmpty() && ok){
            int v = q.poll();
            for (int w : graph[v]) {
                if(!visited[w]){
                    color[w] = !color[v];
                    visited[w] = true;
                    q.offer(w);
                }else{
                    if(color[w] == color[v]){
                        ok = false;
                        break;
                    }
                }
            }
        }
        return ok;
    }
    //广搜的写法
}
